package sh.wnxy.wn38.utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class PathUtils {
    public int M = Integer.MAX_VALUE;

    public Map<String, ArrayList<String>> map = new HashMap<>();
    public int MAXSUM(int a,int b){
        return (a!=M&&b!=M)?(a+b):M;
    }

    public ArrayList<Integer[][]> flody(Integer[][] dist){
        Integer[][] path=new Integer[10][10];//存储的是从i->j经过的最后一个节点
        for (int i = 0; i <= 9; i++) {
            for (int j = 0; j <= 9; j++) {
                path[i][j]=i;
            }
        }
        for(int k=0;k<=9;k++){
            for (int i = 0; i <= 9; i++) {
                for (int j = 0; j <= 9; j++) {
                    if(dist[i][j]>MAXSUM(dist[i][k], dist[k][j])){
                        path[i][j]=path[k][j];//存储的是从i->j经过的最后一个节点
                        dist[i][j]=MAXSUM(dist[i][k], dist[k][j]);
                    }
                }
            }
        }
        ArrayList<Integer[][]> list =new ArrayList<Integer[][]>();
        list.add(dist);
        list.add(path);
        return list;
    }

    public Integer[] reverse(Integer[] chain,int count){
        int temp;
        for(int i=0,j=count-1;i<j;i++,j--){
            temp=chain[i];
            chain[i]=chain[j];
            chain[j]=temp;
        }
        return chain;
    }
    public void display_path(ArrayList<Integer[][]> list){
        Integer[][] dist=list.get(0);
        Integer[][] path=list.get(1);
        Integer[] chain=new Integer[9];
//        System.out.println("orign->dist"+" dist "+" path");


        String name = null;
        for (int i = 0; i <=9; i++) {
            for (int j = 0; j <= 9; j++) {

                if(i!=j){//只是避免了vi->vi的输出
                    //输出源到目的地
                    //0 抱抱龙冲天赛车 1 七个小矮人矿车 2 加勒比海盗 3 创极速光轮 4 漫游童话时光 5 探秘海妖复仇湾 6 巴斯光年星际营救 7 漫威英雄总部 8 雷鸣山漂流 9 飞跃地平线
//                    if(i==0){
//                        name = "抱抱龙冲天赛车";
//                    }else if(i==1){
//                        name = "七个小矮人矿车";
//                    }else if(i==2){
//                        name = "加勒比海盗";
//                    }else if(i==3){
//                        name = "创极速光轮";
//                    }else if(i==4){
//                        name = "漫游童话时光";
//                    }else if(i==5){
//                        name = "探秘海妖复仇湾";
//                    }else if(i==6){
//                        name = "巴斯光年星际营救";
//                    }else if(i==7){
//                        name = "漫威英雄总部";
//                    }else if(i==8){
//                        name = "雷鸣山漂流";
//                    }else{
//                        name = "飞跃地平线";
//                    }
                    name = i+""+j;

//                    System.out.print("\n   "+(i)+"->"+(j)+"     ");
//                    if(j==0){
//                        name += "抱抱龙冲天赛车";
//                    }else if(j==1){
//                        name += "七个小矮人矿车";
//                    }else if(j==2){
//                        name += "加勒比海盗";
//                    }else if(j==3){
//                        name += "创极速光轮";
//                    }else if(j==4){
//                        name += "漫游童话时光";
//                    }else if(j==5){
//                        name += "探秘海妖复仇湾";
//                    }else if(j==6){
//                        name += "巴斯光年星际营救";
//                    }else if(j==7){
//                        name += "漫威英雄总部";
//                    }else if(j==8){
//                        name += "雷鸣山漂流";
//                    }else{
//                        name += "飞跃地平线";
//                    }

                    //输出最短路径的长度
                    ArrayList<String> fPath = new ArrayList<>();
                    if(dist[i][j]==M){
                        fPath.add("NA");
////                        System.out.print(" NA ");
////                        fPath[index++] = " NA ";
                    }else{
//                        System.out.print(dist[i][j]+"      ");
//                        fPath[index++] = dist[i][j]+"";
                    int count=0;
                    int k=j;
                    do {
                        k=chain[count++]=path[i][k];
                    } while (i!=k);
                    chain=reverse(chain,count);
                    //输出路径
//                        String[] fPath = new String[500];
//                        int index = 0;

//                        System.out.print(chain[0]+"");
                    //0 抱抱龙冲天赛车 1 七个小矮人矿车 2 加勒比海盗 3 创极速光轮 4 漫游童话时光 5 探秘海妖复仇湾 6 巴斯光年星际营救 7 漫威英雄总部 8 雷鸣山漂流 9 飞跃地平线
                    if(chain[0]==0){
                        fPath.add("抱抱龙冲天赛车");
                    }else if(chain[0]==1){
                        fPath.add("七个小矮人矿车");
                    }else if(chain[0]==2){
                        fPath.add("加勒比海盗");
                    }else if(chain[0]==3){
                        fPath.add("创极速光轮");
                    }else if(chain[0]==4){
                        fPath.add("漫游童话时光");
                    }else if(chain[0]==5){
                        fPath.add("探秘海妖复仇湾");
                    }else if(chain[0]==6){
                        fPath.add("巴斯光年星际营救");
                    }else if(chain[0]==7){
                        fPath.add("漫威英雄总部");
                    }else if(chain[0]==8){
                        fPath.add("雷鸣山漂流");
                    }else{
                        fPath.add("飞跃地平线");
                    }

                    fPath.add("↓");

                    for(k=1;k<count;k++){
//                            System.out.print("->"+(chain[k]));
                        if(chain[k]==0){
                            fPath.add("抱抱龙冲天赛车");
                        }else if(chain[k]==1){
                            fPath.add("七个小矮人矿车");
                        }else if(chain[k]==2){
                            fPath.add("加勒比海盗");
                        }else if(chain[k]==3){
                            fPath.add("创极速光轮");
                        }else if(chain[k]==4){
                            fPath.add("漫游童话时光");
                        }else if(chain[k]==5){
                            fPath.add("探秘海妖复仇湾");
                        }else if(chain[k]==6){
                            fPath.add("巴斯光年星际营救");
                        }else if(chain[k]==7){
                            fPath.add("漫威英雄总部");
                        }else if(chain[k]==8){
                            fPath.add("雷鸣山漂流");
                        }else{
                            fPath.add("飞跃地平线");
                        }
                        fPath.add("↓");
                    }

//                        System.out.print("->"+j);
                    if(j==0){
                        fPath.add("抱抱龙冲天赛车");
                    }else if(j==1){
                        fPath.add("七个小矮人矿车");
                    }else if(j==2){
                        fPath.add("加勒比海盗");
                    }else if(j==3){
                        fPath.add("创极速光轮");
                    }else if(j==4){
                        fPath.add("漫游童话时光");
                    }else if(j==5){
                        fPath.add("探秘海妖复仇湾");
                    }else if(j==6){
                        fPath.add("巴斯光年星际营救");
                    }else if(j==7){
                        fPath.add("漫威英雄总部");
                    }else if(j==8){
                        fPath.add("雷鸣山漂流");
                    }else{
                        fPath.add("飞跃地平线");
                    }
                    map.put(name,fPath);
                    }
                }
            }
        }
    }

}
